package codingforgreat.class42;

import jdk.nashorn.internal.parser.JSONParser;

import java.util.concurrent.ForkJoinPool;

public class Problem_0296_BestMeetingPoint {
    //二维数组 1代表人 0代表空位置 问从哪里开会人到那里的花销最小
    //人只能上下左右移动
    //思路：最小行 + 最小列
    public static int minTotalDistance(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int[] iOnes = new int[N];//每行有几个1
        int[] jOnes = new int[M];//每列有几个1
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1){
                    iOnes[i]++;
                    jOnes[j]++;
                }
            }
        }
        int i = 0;
        int j = N - 1;
        int total = 0;
        int iRest = 0;
        int jRest = 0;
        while (i < j){
            if (iOnes[i] + iRest <= iOnes[j] + jRest) {
                total += iOnes[i] + iRest;
                iRest += iOnes[i++];
            } else {
                total += iOnes[j] + jRest;
                jRest += iOnes[j--];
            }
        }
         i = 0;
         j = M - 1;
         iRest = 0;
         jRest = 0;
         while (i < j ){
             if(jOnes[i] + iRest <= jOnes[j] + jRest){
                 total += jOnes[i] + iRest;
                 iRest += jOnes[i++];
             }else{
                 total += jOnes[j] + jRest;
                 jRest += jOnes[j--];
             }
         }
        return total;
    }
}
